Traditional mathematics has relied on idealized models of the complicated and irregular forms and physical processes of nature. These idealized models can be described in terms of continuous, differentiable functions and have no stastical basis involved in their generation. Graphics representative of clouds, mountains, coastlines, trees and the like are extremely difficult to describe in such terms. In his book The Fractal Geometry of Nature published by Freeman, San Francisco, in 1982 and included herein by reference, Benoit Mandelbrot describes in detail a new class of functions called fractals to express such irregular, fragmented natural forms.
A fractal function includes both the basic form inherent in a shape and the statistical or random properties of the placement of that shape in space. For example, a cloud may be drawn using overlapping circles. The circle is the basic shape, and the randomly determined size and position of the circles gives the cloud its natural look.
Fractals have the property of self-similarity as the spatial scale is changed over many orders of magnitude. As an example consider a rocky, very jagged coastline. The coastline looks similar seen from a jet airplane (a distance of 10 km), from a low altitude plane (100 m) and or from a standing position (1 m). A mountain is another example of a self-similar form. As the observer comes closer to a mountain, its subpeaks and hills resemble the whole. On a smaller scale the rock faces and clefts which make up the mountain have structure suggestive of the structure of the whole mountain. Considering the clouds, the coastline, or the mountain, one can discern that a basic form or "generator" is represented on multiple spatial scales from huge to minute.
Self-similar structures can have the randomness of a mountain or clouds or they can be geometrically defined and constructed in a more regular fashion. Self-similar structures with an infinite number of spatial scales can be built by starting with a desired structure or "initiator" and purposefully including a second structure, or "generator" at successively smaller spectral scales. The resulting fractal is termed a "teragon". Mandelbrot gives many examples of teragons, both regular and random.
The "usual topological dimension", D.sub.T, is the intuitive Euclidean measure, a dot having D.sub.T =0, a line having D.sub.T =1, a plane having D.sub.T =2, and a cube having D.sub.T =3. The concept of dimension is generalized by Mandelbrot from the usual topological dimension D.sub.T to the Hausdorff, or fractal, dimension D which is suitable for measuring the complicated, sometimes infinitely long extent of a fractal structure. The "similarity dimension" can also be associated with fractal dimension. To paraphrase Mandelbrot's example with regard to this concept of dimension, consider again the rugged, indented coastline. To measure from a detailed map the length of the coast between two points, a straight measuring stick of length .epsilon.=10 km to map scale, a certain distance L=N.epsilon. is measured. However, in using such a coarse measure, certain indentations of the coast must be passed over, and the measurement of L is too small. Measuring again with a stick of length .epsilon.=1 km to map scale, the overall length L increases. As the length of the "measuring stick" shortens, measurements of the coastline can be made directly using surveying instruments, then actual measuring sticks, and then a microscope. As .epsilon..fwdarw.0, and each minute feature is measured, the overall length of the coast approaches infinity. The problem arises because L has been measured in one-dimensional units, L(.epsilon.)=N.epsilon..sup.1. If instead L is measured in units of .epsilon..sup.D, where D is the fractal (Hausdorff) dimension, there is a number D, (1&lt;D&lt;2), such that the measured length L=N.epsilon..sup.D is independent of the value of .epsilon.. The fractal coastline lies somewhere between a series of connected straight segments, which could be measured unambiguously with a one dimensional measuring stick, and a space-filling two dimensional structure, where the usual two-dimensional area measure would be appropriate. The fractal dimension D is somewhere between one and two. A fractal is a structure whose Hausdorff dimension D exceeds its topological dimension D.sub.T. The larger D is compared to D.sub.T, the more convoluted, or "space-filling" or irregular the fractal.
The computer graphics community has recently been looking to fractal geometry as a way of synthesizing natural looking shapes and textures. Prior art fractal generation involves large amounts of computation, typically many minutes or even hours of computer time per image. In most of the simulations, a rule for creating the basic form is specified, and a random-walk-like statistical process is started. A large number of steps is performed, and a fractal image is the end product. An overview of the prior art usage of fractals in image synthesis is provided by Alex Pentland in his article "Fractal-Based Description of Natural Scenes" in I.E.E.E. Transactions on Pattern and Machine Intelligence, Vol. PAMI-6, No. 6, November, 1984, pp. 661-674. Another overview is provided by A. Fournier, D. Fussell, and L. Carpenter in their article "Computer Rendering of Stochastic Models" appearing on pages 371-384 of Communications of the ACM, Vol. 25, No. 6, June 1982. A less cumbersome way of generating fractals, which would allow their computation in shorter time is desirable. It is desirable that the method be one that can be implemented in digital hardware for generating fractals in real time at normal television scan rates.
The present invention centers around a new, vastly more efficient method for generating fractals, which method is in the nature of teragon construction. The method depends on an insight of the present inventor that the self-similarity property of fractals can be related to a self-similarity property that exists in inverse pyramid transforms.
Pyramid and inverse pyramid transforms are described, for example, by P. J. Burt in "The Pyramid as a Structure for Efficient Computation" in IPL-TR-038 published by the Image Processing Laboratory, Electrical and Systems Engineering Department, Rensselaer Polytechnic Institute, Troy, NY 12181. Inverse pyramid transforms are more specifically described by P. J. Burt and E. H. Adelson in "A Multiresolution Spline with Application to Image Mosaics", ACM Transactions on Graphics, Vol. 2, No. 4, October 1983, pp. 217-236.
The Burt pyramid transform is a spectrum analysis algorithm that separates a signal into spatial-frequency band-pass components, each approximately an octave wide in one or more dimensions and a remnant low-pass component. The band-pass components have successively lower center frequencies and successively less dense sampling in each dimension, each being halved from one band-pass component to the next lower. The remnant low-pass component may be sampled with the same density as the lowest band-pass component or may be sampled half so densely in each dimension. Processes that operate on the transform result components affect, on different scales, the reconstruction of signal in an inverse transform process. Processes operating on the lower-spatial-frequency, more-sparsely-sampled transform result components affect the reconstructed signal over a larger region than do processes operating on the higher-spatial frequency, more-densely-sampled transform result components. This comes about because of the nature of the inverse pyramid transform.
In the inverse pyramid process, the more-sparsely-sampled transform result components (as possibly modified) are expanded through interpolation to be sampled at the same density as the most-densely-sampled transform result. The expanded transform result components, now sampled at similar sampling density, are linearly combined by simple matrix summation. That is, there is a summing together of the expanded transform result components at each corresponding sample location in the most-densely-sampled sample space, which they share.
Because of associative and distributive properties in this expansion and linear combination process, this process is most efficiently carried out as follows. The most-sparsely-sampled transform result component is expanded to the same sampling density as the second-least-densely-sampled transform result component, then linearly combined with the second-least-densely-sampled transform result component, to obtain the linear combination of the two transform result components at the second-least-dense sampling periodicity. This linear combination of the two transform result components is expanded to the same sampling density as the third-least-densely-sampled transform result component and linearly combined therewith to obtain the linear combination of the three transform result components at the third-least-dense sampling periodicity. This successive stepwise expansion and linear combination continues until the linear combination of all the transform result components at the most-dense-sampling periodicity (the sampling periodicity of the highermost-octave transform result component) is obtained.
R. W. Schaefer and L. R. Rabiner describe a good way of performing interpolation of sample-data functions in their paper "A Digital Signal Processing Approach to Interpolation" appearing in PROCEEDINGS OF THE IEEE Vol. 61, No. 6, June 1973, pp. 692-702. Sparse sampling matrices have nulls inserted between sample data to develop denser sampling matrices, and the spurious harmonic frequencies generated by null insertion are removed by low-pass filtering.